TNotes.leetcode

Appearance

0821. 字符的最短距离【简单】

0821. 字符的最短距离【简单】 ​

1. 📝 题目描述 ​

  • 给你一个字符串 s 和一个字符 c，且 c 是 s 中出现过的字符。
  • 返回一个整数数组 answer，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离。
  • 两个下标 i 和 j 之间的 距离 为 abs(i - j)，其中 abs 是绝对值函数。

示例 1：

  • 输入：s = "loveleetcode", c = "e"
  • 输出：[3,2,1,0,1,0,0,1,2,2,1,0]
  • 解释：
    • 字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
    • 距下标 0 最近的 'e' 出现在下标 3，所以距离为 abs(0 - 3) = 3。
    • 距下标 1 最近的 'e' 出现在下标 3，所以距离为 abs(1 - 3) = 2。
    • 对于下标 4，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1。
    • 距下标 8 最近的 'e' 出现在下标 6，所以距离为 abs(8 - 6) = 2。

示例 2：

  • 输入：s = "aaab", c = "b"
  • 输出：[3,2,1,0]

提示：

  • 1 <= s.length <= 10^4
  • s[i] 和 c 均为小写英文字母
  • 题目数据保证 c 在 s 中至少出现一次

2. 🎯 s.1 - 两次遍历（从左到右 + 从右到左） ​

js
/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function (s, c) {
  const n = s.length
  const result = new Array(n)

  // 从左到右遍历，计算每个位置到左侧最近的c的距离
  let prev = -Infinity
  for (let i = 0; i < n; i++) {
    if (s[i] === c) {
      prev = i
    }
    result[i] = i - prev
  }

  // 从右到左遍历，计算每个位置到右侧最近的c的距离，并取较小值
  prev = Infinity
  for (let i = n - 1; i >= 0; i--) {
    if (s[i] === c) {
      prev = i
    }
    result[i] = Math.min(result[i], prev - i)
  }

  return result
}
  • 时间复杂度：O(n)，其中 n 是字符串的长度，需要进行两次遍历
  • 空间复杂度：O(1)，不考虑结果数组的话，只使用了常数个额外变量
  • 算法思路：
    • 对于每一个字符 s[i]，距离它最近的字符 c 要么出现在左边，要么出现在右边。
    • 可以通过两次遍历分别计算每个位置 i 的字符 s[i] 到其左侧和右侧最近目标字符 c 的距离，取最小值作为最终结果。

3. 🎯 s.2 - 中心扩展法 ​

js
/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function (s, c) {
  const n = s.length
  const result = new Array(n).fill(Infinity)

  // 找到所有c的位置
  const positions = []
  for (let i = 0; i < n; i++) {
    if (s[i] === c) {
      positions.push(i)
    }
  }

  // 对每个c的位置，向两边扩展更新距离
  for (const pos of positions) {
    for (let i = 0; i < n; i++) {
      result[i] = Math.min(result[i], Math.abs(i - pos))
    }
  }

  return result
}
  • 时间复杂度：O(n×k)，其中 n 是字符串长度，k 是字符 c 的个数
  • 空间复杂度：O(1)，不考虑结果数组的话，只使用了常数个额外变量
  • 算法思路：
    • 【1】找到所有目标字符的位置
    • 【2】以每个目标字符作为中心，向左右两边扩展，计算距离
    • 【3】取最小值作为最终结果

Discussions